package com.wp.InterviewAlgorithm.lesson1;


import com.wp.utils.LinkedListUtil;
import com.wp.utils.LinkedListUtil.Node;

import static com.wp.utils.LinkedListUtil.printNodeExceptFirst;
/**
 * Created by 王萍 on 2017/9/18 0018.
 */

/**
 * 给定排序的链表，删除重复的元素，
 * 1.只保留元素第一次出现的节点。
 * 如：输入，2->3->3->5->7->8->8->8->9->9->10
 * 输出：  2->3->5->7->8->9->10
 * <p>
 * 2.不保留重复出现的元素。
 * 如：输入，2->3->3->5->7->8->8->8->9->9->10
 * 输出：  2->5->7->10
 */
public class 排序链表中去重 {

    public static void main(String[] args) {

        Node node = LinkedListUtil.produceSortedList(27);
        Node specialHead = new Node(Integer.MIN_VALUE);
        specialHead.next = node;
        printNodeExceptFirst(node);
//        Node result = deleteRepeatedElementRemainsOne(node);
//        System.out.println("去重且保留一个元素为：");
//        printNode(result);
        System.out.println("去重且不保留元素为：");
        printNodeExceptFirst(deleteAllRepeatedElement(node));
    }

    private static Node deleteRepeatedElementRemainsOne(Node root) {

        if (root == null) return null;

        Node currentNode = root;
        while (currentNode.next != null) {
            if (currentNode.value == currentNode.next.value) {
                Node nextNode = currentNode.next;
                currentNode.next = nextNode.next;
                nextNode.next = null;
            } else {
                currentNode = currentNode.next;
            }
        }
        return root;
    }

    //巧妙的记录了当前节点的前节点。
    private static Node deleteAllRepeatedElement(Node root) {

        if (root == null) return null;

        Node pPre = root;                       //表示当前节点的前节点
        Node pCur = pPre.next;               //表示当前节点
        Node pNext;                                //表示当前节点的后节点
        boolean repeated;
        //每删除一个节点后都需要，更新pPre,pCur,pNext节点的位置。
        while (pCur != null) {
            pNext = pCur.next;
            repeated = false;
            while (pNext != null && (pCur.value == pNext.value)) {
                pPre.next = pNext;
                pCur = pNext;
                pNext = pCur.next;
                repeated = true;
            }
            if (repeated) {  //执行这里表示执行了上面的while
                pPre.next = pNext;
            } else {
                pPre = pCur;
            }
            pCur = pNext;
        }
        return root;
    }
}
